﻿#pragma once

#include<iostream>
using namespace std;


template<class K>
struct BSTNode//节点
{
	K _key;//key
	BSTNode<K>* _left;//结构体装结构体指针//左
	BSTNode<K>* _right;//右

	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

template<class K>
class BSTree//树
{
	typedef BSTNode<K> Node;//节点换名Node
public:
	bool Insert(const K& key)//插入：(想要插入后有完整的链接：)
		//查找到这个空位置时，还需要知道其父亲：双指针
		//双指针：cur，parent
	{
		//如果是空树，需要先给它new一个节点直接装key/否则后续的程序出现根节点（空树）为空就无法执行
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		//给双指针
		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			//找到此值应该在的位置
			//每次往左下走还是往右下走，都用cur赋值给parent（此后再向后走）的方法，保证能准确跟踪cur的parent
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//左右都没有它能呆的位置：已存在
				//else 部分：当 cur->_key 既不小于也不大于 key 时，即相等，返回 false，可能表示要查找的 key 已经存在于树中，不允许重复插入。
			{
				return false;
			}
		}

		//找到位置后放节点new（还要链接：区分左右：加个判断）
		cur = new Node(key);//new出来的节点给cur这个位置
		//再和父亲链接:分左指针/右指针
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)//根小于要找的key（左边不可能）//往右找
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_right;
			}
			else//相等找到
			{
				return true;
			}
		}
		//走完都没返回true
		//那就找不到
		return false;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	//搜索二叉树默认情况下不进行修改（可能破坏结构），但是变形后可以
	
	//删除
	//考虑删除的节点的子情况
	// 1，有一个儿子（被删掉的是根的左（就用parent左链接）/否则就用->right链接）
	//      2，有两边子树（用左树的最大/右树最小；去替代被删的位置）
	//         上位：置左右指针和被删的节点相同，上位的节点的parent需要链接下一个/or nullptr
	// 3，没有儿子（叶节点）free（再parent->left/right置空）
	//
	//同样需要知道父亲（双指针）
	
	bool Erase(const K& key)
	{
		//给双指针
		Node* parent = nullptr;
		Node* cur = _root;

		//找到需要删除的位置
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//找到：开删
			{
				//一个孩子/没有孩子（有一边为空）
				if (cur->_left == nullptr)
					//被删节点的左为空：让父亲（的左/右）指向这个被删节点的右指针
					//被删节点是左儿子，就让父亲的左☞右/
					//被删节点是右儿子，就让父亲的右☞右/
				{
					//左为空，就让根变成现在（根）的右（也就是将根删除）
					//根向右下移动，跳过需要删除的根
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
					return true;
				}
				else if(cur->_right == nullptr)
				{
					//右为空，就让根变成现在（根）的左（也就是将根删除）
					//根向左下移动，跳过需要删除的根
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
					return true;
				}
				//左空，右空，都空（叶子）已走/
				//剩下左右都有的情况
				//找替代节点（右最小，左最大）
				else
				{
					Node* rightMinP = cur;
					Node* rightMin = cur->_right;
					//先假定被删节点的右子节点是右最小
					//右树的最小肯定存在在最左的节点里，只要有左，就将这个左赋值给假定的（暂时的）最小
					while (rightMin->_left)
					{
						rightMinP = rightMin;//往下走之前，把当前这个值给父亲
						rightMin = rightMin->_left;
					}
					//找到最左节点之后，赋值（替换）
					cur->_key = rightMin->_key;
					//找到右树最左（最小）
					//现在就该删除这个rightMin
					//删除需要知道它的父亲，加上父亲(节点往后走，父亲也往后走)

					//因为min是最左节点（无左子树），所以肯定是将min的右子树链接到parent的左指针
					
					//替换，衔接链接两种情况
					if (rightMinP->_left == rightMin)//如果被替换的rightMin和它的父亲是左指向的关系
					{//那么就让p的左指针，指向这个min的右指针（接min的右边：因为其为最左）
						rightMinP->_left = rightMin->_right;
					}
					else
						rightMinP->_right = rightMin->_right;//最小节点的父亲就是这个被替换的节点，直接将父亲的右指针链接自己的右指针，跳过自己

					//***************************************
					//如果这个原始的cur->right就是右树最小
					// 不进循环
					//那么上面这一行就有问题
					//cur的左树被接到了（被右树覆盖）右树
					//所以：rightMin


					//链接后删除节点min
					delete rightMin;
					return true;
				}
			}
		}
		return false;
	}
	
private:

	//中序：左根右
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		std::cout << root->_key << " "; // 访问根节点
		_InOrder(root->_right);
	}


	Node* _root = nullptr;//根
};


//排序+二分查找（查找次数可以折半）：底层是数组：插入和删除代价很大
//搜索树 -> 二叉搜索树（插入和删除代价比较小，只需要链接）不需要每个都挪动   O(N)
//         平衡树/（AVL树，红黑树） O(logN)
//         多叉平衡搜索树（M阶的B树系列）
//         哈希系列
//         
// key  ->   在不在    门🈲（人脸...）
// 
// key/value   ->  通过一个值找另一个值（也是在不在）
//  *****************************************************************************************************

namespace keyValue
{
	template<class K ,class V>
	struct BSTNode//节点
	{
		K _key;
		V _value;
		BSTNode<K,V>* _left;
		BSTNode<K,V>* _right;

		BSTNode(const K& key,const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};

	template<class K,class V>
	class BSTree//树
	{
		typedef BSTNode<K,V> Node;//节点换名Node
	public:
		//如果没有写任何的构造函数，就会自动生成
		//如果写了拷贝构造，原来的自动生成的默认构造就不能用了
		//不想写，可以强制生成：使用default
		BSTree() = default;


		//拷贝构造
		BSTree(const BSTree<K, V>& t)
		{
			_root = Copy(t._root);//用Copy函数内部递归完成拷贝
		}

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;

			//value不参与key的比较大小（只是一个附带的内容）
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(key, value);

			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)//根小于要找的key（左边不可能）//往右找
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_right;
				}
				else//相等找到
				{
					return cur;
				}
			}
			//走完都没返回true
			//那就找不到
			return nullptr;
		}

		

		//搜索二叉树默认情况下不进行修改（可能破坏结构），但是变形后可以

		//删除
		//考虑删除的节点的子情况
		// 1，有一个儿子（被删掉的是根的左（就用parent左链接）/否则就用->right链接）
		//      2，有两边子树（用左树的最大/右树最小；去替代被删的位置）
		//         上位：置左右指针和被删的节点相同，上位的节点的parent需要链接下一个/or nullptr
		// 3，没有儿子（叶节点）free（再parent->left/right置空）
		//
		//同样需要知道父亲（双指针）

		bool Erase(const K& key)
		{
			//给双指针
			Node* parent = nullptr;
			Node* cur = _root;

			//找到需要删除的位置
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else//找到：开删
				{
					//一个孩子/没有孩子（有一边为空）
					if (cur->_left == nullptr)
						//被删节点的左为空：让父亲（的左/右）指向这个被删节点的右指针
						//被删节点是左儿子，就让父亲的左☞右/
						//被删节点是右儿子，就让父亲的右☞右/
					{
						//左为空，就让根变成现在（根）的右（也就是将根删除）
						//根向右下移动，跳过需要删除的根
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						//右为空，就让根变成现在（根）的左（也就是将根删除）
						//根向左下移动，跳过需要删除的根
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
						return true;
					}
					//左空，右空，都空（叶子）已走/
					//剩下左右都有的情况
					//找替代节点（右最小，左最大）
					else
					{
						Node* rightMinP = cur;
						Node* rightMin = cur->_right;
						//先假定被删节点的右子节点是右最小
						//右树的最小肯定存在在最左的节点里，只要有左，就将这个左赋值给假定的（暂时的）最小
						while (rightMin->_left)
						{
							rightMinP = rightMin;//往下走之前，把当前这个值给父亲
							rightMin = rightMin->_left;
						}
						//找到最左节点之后，赋值（替换）
						cur->_key = rightMin->_key;
						//找到右树最左（最小）
						//现在就该删除这个rightMin
						//删除需要知道它的父亲，加上父亲(节点往后走，父亲也往后走)

						//因为min是最左节点（无左子树），所以肯定是将min的右子树链接到parent的左指针

						//替换，衔接链接两种情况
						if (rightMinP->_left == rightMin)//如果被替换的rightMin和它的父亲是左指向的关系
						{//那么就让p的左指针，指向这个min的右指针（接min的右边：因为其为最左）
							rightMinP->_left = rightMin->_right;
						}
						else
							rightMinP->_right = rightMin->_right;//最小节点的父亲就是这个被替换的节点，直接将父亲的右指针链接自己的右指针，跳过自己

						//***************************************
						//如果这个原始的cur->right就是右树最小
						// 不进循环
						//那么上面这一行就有问题
						//cur的左树被接到了（被右树覆盖）右树
						//所以：rightMin


						//链接后删除节点min
						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}

		
	

	private:
		//中序：左根右
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			std::cout << root->_key<< " " << root->_value << " "; // 访问根节点
			_InOrder(root->_right);
		}

		void Destroy(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			Destroy(root->_left);

			Destroy(root->_right);
			//先销毁左右/再销毁根
			delete root;
		}

		Node* Copy(Node* root)//传根节点/返回拷贝后的根节点地址
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			//先深拷贝一个新的根节点/再递归拷贝左的根/右的根
			Node* newRoot = new Node(root->_key, root->_value);
			newRoot->_left = Copy(root->_left);
			newRoot->_right = Copy(root->_right);

			return newRoot;
		}

		

		private:
		Node* _root = nullptr;//根
	};

}









